#include<stdio.h>
#include<conio.h>
#include<time.h>
void nhap(int a[],int &n)
{
	printf("nhap so phan tu: ");
	scanf("%d",&n);
	for(int i=0;i<=n-1;i++)
	{
		printf("a[%d] = ",i);
		scanf("%d",&a[i]);
	}
}
void xuat(int a[],int n)
{
	for(int i=0;i<=n-1;i++)
		printf("  %d\t|",a[i]);
}
void xuatQS(int a[],int l,int r, int n, int m)
{
    for(int i=0;i<=n-1;i++)
		if (i==m) printf(" (%2d)\t|",a[i]);
		else	
			if (i>=l&&i<=r)printf(" %2d\t|",a[i]);
			else printf("\t|");
	
}
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
void Interchangesort(int a[],int n)
{
    printf("\n\t");
    for(int i=0;i<=n-1;i++)
	    printf("  %d\t|",i);
	for(int i=0;i<=n-2;i++)
	{
        printf("\n---------------------------------------------------------------------------");   
		printf("\nBuoc %d: ",i);
		xuat(a,n);
		for(int j=i+1;j<=n-1;j++)
			if(a[i]>a[j])
				swap(a[i],a[j]);
	}
	printf("\n---------------------------------------------------------------------------");   
	printf("\nKet qua:");
}
void Selectionsort(int a[],int n)
{
    printf("\n\t");
    for(int i=0;i<=n-1;i++)
	    printf("  %d\t|",i);
	for (int i=0;i<=n-2;i++)
	{
        printf("\n---------------------------------------------------------------------------");   
		printf("\nBuoc %d:",i);
		xuat(a,n);
		int min=i;
		for(int j=i+1;j<=n-1;j++)
			if(a[min]>a[j])
				min=j;
		swap(a[min],a[i]);
	}
	
    printf("\n---------------------------------------------------------------------------");   
	printf("\nKet qua:");
}
void Bubblesort(int a[],int n)
{
    printf("\n\t");
    for(int i=0;i<=n-1;i++)
	    printf("  %d\t|",i);
	for(int i=0;i<n-2;i++)
	{            
        printf("\n---------------------------------------------------------------------------");   
		printf("\nBuoc %d:",i);
		xuat(a,n);
		for(int j=n-1;j>=i+1;j--)
			if(a[j]<a[j-1])
				swap(a[i],a[j-1]);
	}
	
    printf("\n---------------------------------------------------------------------------");   
	printf("\nKet qua:");
}

void Quicksort(int a[],int l,int r,int n)
{
	int i,j,x,m;
	m=(l+r)/2;x=a[m];
	i=l;
	j=r;
	printf("\nl=%d,r=%d,x=a[%d]=%d\t|",l,r,(l+r)/2,a[(l+r)/2]);xuatQS(a,l,r,n,m);
	printf("\n----------------------------------------------------------------------------------------------\n");
	do
	{
		while(a[i]<x)
			i++;
		while(a[j]>x)
			j--;
		if(i<=j)
		{
			if (i==m) m=j;
			else 
				if(j==m) m=i;
			swap(a[i],a[j]);
			printf("\t\t\t");xuatQS(a,l,r,n,m);
			printf("\n----------------------------------------------------------------------------------------------\n");
			i++;
			j--;
		}
	}while(i<=j);
	if(l<j)
		Quicksort(a,l,j,n);
	if(i<r)
		Quicksort(a,i,r,n);
}
int main()
{   clock_t start, finish;
    start = clock();
   	int a[100],n,chon,flag=0;
	printf("\n1.Nhap danh sach");
	printf("\n2.Xuat danh sach");
	printf("\n3.Sap xep bang Interchangesort");
	printf("\n4.Sap xep bang Selectionsort");
	printf("\n5.Sap xep bang Bubblesort");
	printf("\n6.Sap xep bang Quicksort");
	printf("\n0.Thoat");
	do
	{
		printf("\n\nBan chon:");
		scanf("%d",&chon);
		switch(chon)
		{
			case 1:
			nhap(a,n);
			flag=1;
			break;
			case 2: 
				if(flag=0)
					printf("Ban chua nhap danh sach");
				else
					xuat(a,n);
				break;
			case 3:
				if(flag=0)
					printf("Ban chua nhap danh sach");
				else
				{
					Interchangesort(a,n);
					xuat(a,n);
				}
				break;
			case 4:
				if(flag=0)
					printf("Ban chua nhap danh sach");
				else
				{
					Selectionsort(a,n);
					xuat(a,n);
				}
				break;
			case 5:
				if(flag=0)
					printf("Ban chua nhap danh sach");
				else
				{
					Bubblesort(a,n);
					xuat(a,n);
				}
				break;
			case 6:
				if(flag=0)
					printf("Ban chua nhap danh sach");
				else
				{
                    printf("\n\t\t\t");
                    for(int i=0;i<=n-1;i++)
	                   printf("  %d\t|",i);
                   	printf("\n----------------------------------------------------------------------------------------------\n");
					Quicksort(a,0,n-1,n);
					printf("\nKet qua:\t\t|");
					xuat(a,n);
				}
				break;
		}
	}while(chon!=0);
	finish = clock();
    printf("Time for sort (seconds): %f",((double)(finish - start))/CLOCKS_PER_SEC);
	getch();
	return 0;
}